package queue_stack.leetcode.medium;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author bruin_du
 * @description 出现频率最高的 k 个数字
 * @date 2022/8/16 22:24
 **/
public class OfferII060_TopKFrequent {
    //或者使用Map保存数据也可以
    static class Node implements Comparable<Node>{
        int val;
        int times;

        public Node(int val, int times) {
            this.val = val;
            this.times = times;
        }

        @Override
        public int compareTo(Node node) {
            return node.times - times;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        Arrays.sort(nums);
        int prev = nums[0];
        Node node = new Node(nums[0], 0);
        Queue<Node> queue = new PriorityQueue<>();
        for (int x : nums) {
            if (x == prev) {
                node.times++;
            } else {
                prev = x;
                queue.offer(node);
                node = new Node(x, 1);
            }
        }
        queue.offer(node);
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll().val;
        }
        return res;
    }
}
